package Test;

import java.util.Arrays;

public class 跳跃问题 {

    /*********11111111111111111111******/
    //能否跳到最后
    public boolean canJump(int[] nums) {
       int n=nums.length;
       int max=0;
       for (int i=0;i<n-1;i++){
           max=Math.max(max,nums[i]+i);
           if(max==i) return false;
       }
       return max>=n-1?true:false;
    }


    //跳到最后最少几步
    /********动态规划********/
    int[] memo;
    // 主函数
    public int jump(int[] nums) {
        int n = nums.length;
        // 备忘录都初始化为 n，相当于 INT_MAX
        // 因为从 0 跳到 n - 1 最多 n - 1 步
        memo = new int[n];
        Arrays.fill(memo, Integer.MAX_VALUE);

        return dp(nums, 0);
    }

    // 定义：从索引 p 跳到最后一格，至少需要 dp(nums, p) 步
    int dp(int[] nums, int p) {
        int n = nums.length;
        // base case
        if (p >= n - 1) {
            return 0;
        }
        // 子问题已经计算过
        if (memo[p] != Integer.MAX_VALUE) {
            return memo[p];
        }
        int steps = nums[p];
        // 你可以选择跳 1 步，2 步...
        for (int i = 1; i <= steps; i++) {
            // 穷举每一个选择
            // 计算每一个子问题的结果
            int subProblem = dp(nums, p + i);
            // 取其中最小的作为最终结果
            memo[p] = Math.min(memo[p], subProblem + 1);
        }
        return memo[p];
    }

    /*****************贪心*******************/
    public static int jump1(int[] nums) {
        int n=nums.length;
        int step=0;
        int end=0;
        int s=0;
        for (int i=0;i<n-1;i++){

            step=Math.max(step,nums[i]+i);
            if(end==i){
                s++;
                end=step;
            }
        }
        return s;
    }

    public static void main(String[] args) {
        int[] nums={2,3,1,1,4};
        System.out.println(jump1(nums));
    }
}
